package code.class2;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/find-k-th-smallest-pair-distance/description/
 * 找出第 K 小的数对距离
 * <p>
 * 示例 1：
 * 输入：nums = [1,3,1], k = 1  输出：0
 * 解释：数对和对应的距离如下：
 * (1,3) -> 2
 * (1,1) -> 0
 * (3,1) -> 2
 * 距离第 1 小的数对是 (1,1) ，距离为 0 。
 * <p>
 * 示例 2：
 * 输入：nums = [1,1,1], k = 2 输出：0
 * <p>
 * 示例 3：
 * 输入：nums = [1,6,1], k = 3 输出：5
 */
public class Code04_findKthSmalest {
    public static void main(String[] args) {
        int[] arr = {1, 2, 54, 6, 3, 4, 56, 6, 7, 34, 4, 5, 1, 6, 8, 9, 0};
        int k = 3;
        int kthSmalest = findKthSmalest(arr, k);
        System.out.println("kthSmalest = " + kthSmalest);
    }

    // 通过判断 cnt >= k，可以确定第 k 小的数对距离是否在当前搜索范围内，从而调整二分查找的范围，最终找到第 k 小的数对距离。
    public static int findKthSmalest(int[] arr, int k) {
        // l 是数对距离的最小可能值，而 0 是数对距离的最小值（当两个数相等时，距离为 0）。
        // r 是数对距离的最大可能值，即数组中最大元素与最小元素的差值
        // 因为数对距离的最小值可能是 0
        // 因为数对距离的最大值不会超过数组中最大元素与最小元素的差值，所以 r 设置为 arr[len - 1] - arr[0]。
        Arrays.sort(arr);
        int l = 0, r = arr[arr.length - 1] - arr[0], ans = 0;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            // cnt 表示距离小于等于 m 的数对数量。
            int cnt = f(arr, m);
            // cnt >= k 的含义：如果距离小于等于 m 的数对数量大于或等于 k，说明第 k 小的数对距离可能小于或等于 m。
            if (cnt >= k) {
                ans = m;
                r = m - 1;
            } else {
                // **当 cnt < k 时，说明当前的距离 m 太小，无法包含第 k 小的数对距离。
                // 因此，我们需要增大 m，即调整搜索范围的下限 l。
                l = m + 1;
            }
        }

        return ans;
    }

    private static int f(int[] arr, int limit) {
        int l = 0, r = 0, ans = 0;
        // 滑动窗口问题
        // l和r 从左边开始走，
        while (l < arr.length) {
            // r+1 不超过数组，并且[r+1] -[l]的值在范围内，r向右走
            while (r + 1 < arr.length && arr[r + 1] - arr[l] <= limit) {
                r++;
            }
            // 当超过时，r-l就是当前符合限制的数量
            ans += r - l;
            l++;
        }
        return ans;
    }
    /**
     * 假设数组 arr = [1, 3, 1]，k = 2。
     *
     * 排序数组：arr = [1, 1, 3]。
     *
     * 初始化：
     *
     * l = 0（最小距离）。
     * r = 3 - 1 = 2（最大距离）。
     * 二分查找过程：
     *
     * 第一次循环：
     * m = 0 + (2 - 0) / 2 = 1。
     * 计算 cnt，即距离小于等于 1 的数对数量：
     * |1 - 1| = 0（距离为 0）。
     * |1 - 3| = 2（距离为 2）。
     * |1 - 3| = 2（距离为 2）。
     * cnt = 1（只有 0 小于等于 1）。
     * 因为 cnt = 1 < k = 2，所以 l = m + 1 = 2。
     * 第二次循环：
     * m = 2 + (2 - 2) / 2 = 2。
     * 计算 cnt，即距离小于等于 2 的数对数量：
     * |1 - 1| = 0（距离为 0）。
     * |1 - 3| = 2（距离为 2）。
     * |1 - 3| = 2（距离为 2）。
     * cnt = 3（0 和两个 2 都小于等于 2）。
     * 因为 cnt = 3 >= k = 2，所以 ans = m = 2，r = m - 1 = 1。
     * 循环结束，因为 l = 2 > r = 1。
     * 结果：第 2 小的距离是 2。
     */
}
